#include <vector>
#include <cstdlib>
#include <stack>
using namespace std;

int getMidi(vector<int>& v, int begin, int end, int mid)
{
	if(v[begin] > v[end])
	{
		if(v[begin] > v[mid])
		{
			if(v[mid] > v[end]) return mid;
			else return end;
		}
		else return begin;
	}
	else
	{
		if(v[end] > v[mid])
		{
			if(v[begin] > v[mid]) return begin;
			else return mid;
		}
		else return end;
	}
}

//霍尔版本
void _QuickSort1(vector<int>& v, int begin, int end)
{
	if(begin >= end) return;

	int keyi = getMidi(v, begin, end, begin + (end - begin) / 2);  //三数取中
	//int keyi = rand() % (end - begin + 1) + begin ; // 随机值法
	swap(v[keyi], v[begin]);
	int left = begin, right = end, base = v[begin];

	while(left < right)
	{
		while(base < v[right]) right--;
		while(left < right && v[left] <= base) left++;
		swap(v[left], v[right]);
	}
	base = left;
	swap(v[base] , v[begin]);

	_QuickSort1(v, begin, base - 1);
	_QuickSort1(v, base + 1, end);
}

//快慢指针法
void _QuickSort2(vector<int>& v, int begin, int end)
{
	if(begin >= end) return;

	int keyi = getMidi(v, begin, end, begin + (end - begin) / 2);  //三数取中
	swap(v[keyi], v[begin]);
	int prev = begin, cur = begin + 1, key = v[begin];
	while(cur <= end)
	{
		if(v[cur] < key && ++prev != cur) swap(v[prev], v[cur]);
		cur++;
	}
	swap(v[begin], v[prev]);
	keyi = prev;
	_QuickSort2(v, begin, keyi - 1);
	_QuickSort2(v, keyi + 1, end);
}

void QuickSort(vector<int>& v)
{
	int sz = v.size();
	_QuickSort2(v, 0, sz - 1);
}

void QuickSortNonR(vector<int>& v)
{
	int sz = v.size(), begin, end, prev, cur, key, keyi;
	stack<pair<int, int>> st;
	st.push({0, sz - 1});
	while(! st.empty())
	{
		begin = st.top().first, end = st.top().second;
		st.pop();
		prev = begin, cur = begin + 1, key = v[begin];
		keyi = getMidi(v, begin, end, begin + (end - begin) / 2);  //三数取中
		swap(v[keyi], v[begin]);
		while(cur <= end)
		{
			if(v[cur] < key && ++prev < cur) swap(v[cur], v[prev]);
			cur++;
		}
		swap(v[begin], v[prev]);
		keyi = prev;
		if(begin < keyi - 1) st.push({begin,keyi - 1});
		if(keyi + 1 < end) st.push({keyi + 1, end});
	}
}
